# -*- coding: utf-8 -*-            
# @Time : 2022/11/23 21:54
# @Author  : lining
# @FileName: 链表找环.py
"""
快慢指针法，一个指针一次走一步，一个指针一次走两两步，有环就一定会相遇
https://leetcode.cn/problems/linked-list-cycle/description/
"""
class Node():
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next


class Solution():
    def findcycle(self, head):
        """
        边界问题：如果没有环，那么必定fast先取到最后一个，fast可能取到none，也可能取到none的后一个
        :param head: 头结点，Node类型
        :return:
        """
        fast = head
        slow = head
        # 没有环不是fast是none就是fast.next是none
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast is slow:
                print('有环')
                return True
        return False


a = Node(1)
b = Node(2)
a.next = b
Solution().findcycle(a)
